/**
 *  ElementInteger.java 
 *  This file is part of JaCoP.
 *
 *  JaCoP is a Java Constraint Programming solver. 
 *	
 *	Copyright (C) 2000-2008 Krzysztof Kuchcinski and Radoslaw Szymanek
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Affero General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Affero General Public License for more details.
 *  
 *  Notwithstanding any other provision of this License, the copyright
 *  owners of this work supplement the terms of this License with terms
 *  prohibiting misrepresentation of the origin of this work and requiring
 *  that modified versions of this work be marked in reasonable ways as
 *  different from the original version. This supplement of the license
 *  terms is in accordance with Section 7 of GNU Affero General Public
 *  License version 3.
 *
 *  You should have received a copy of the GNU Affero General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */


package JaCoP.constraints;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Hashtable;

import JaCoP.core.IntDomain;
import JaCoP.core.IntVar;
import JaCoP.core.IntervalDomain;
import JaCoP.core.Store;
import JaCoP.core.ValueEnumeration;
import JaCoP.core.Var;

/**
 * ElementInteger constraint defines a following relation
 * values[index - shift] = value. 
 * 
 * @author Radoslaw Szymanek and Krzysztof Kuchcinski
 * @version 2.4
 */

public class ElementInteger extends Constraint {

	static int idNumber = 1;

	boolean firstConsistencyCheck = true;
	int firstConsistencyLevel;

	
	/**
	 * It specifies variable index within an element constraint list[index-indexOffset] = value.
	 */
	public IntVar index;

	/**
	 * It specifies variable value within an element constraint list[index-indexOffset] = value.
	 */
	public IntVar value;

	/**
	 * It specifies indexOffset within an element constraint list[index-indexOffset] = value.
	 */
	public int indexOffset = 0;

	/**
	 * It specifies list of variables within an element constraint list[index-indexOffset] = value.
	 * The list is addressed by positive integers (>=1) if indexOffset is equal to 0. 
	 */
	public int list[];

	Hashtable<Integer, IntDomain> mappingValuesToIndex = new Hashtable<Integer, IntDomain>();

	boolean indexHasChanged = true;
	boolean valueHasChanged = true;

	/**
	 * It holds information about the positions within list array that are equal. It allows
	 * to safely skip duplicates when enumerating index domain. 
	 */
	ArrayList<IntDomain> duplicates;
	
	/**
	 * It specifies the arguments required to be saved by an XML format as well as 
	 * the constructor being called to recreate an object from an XML format.
	 */	
	public static String[] xmlAttributes = {"index", "list", "value", "indexOffset"};

	/**
	 * It constructs an element constraint. 
	 * 
	 * @param index variable index
	 * @param list list of integers from which an index-th element is taken
	 * @param value a value of the index-th element from list
	 * @param indexOffset shift applied to index variable. 
	 */
	public ElementInteger(IntVar index, int[] list, IntVar value, int indexOffset) {
		
		commonInitialization(index, list, value, indexOffset);
		
	}
	
	void commonInitialization(IntVar index, int[] list, IntVar value, int indexOffset) {

		assert (index != null) : "Variable index is null";
		assert (list != null) : "Variable list is null";
		assert (value != null) : "Variable value is null";
		
		this.indexOffset = indexOffset;
		
		this.numberId = idNumber++;
		this.index = index;
		this.value = value;
		this.numberArgs = (short) (numberArgs + 2);
		this.list = new int[list.length];
		this.queueIndex = 1;
		
		for (int i = 0; i < list.length; i++) {
						
			Integer listElement = list[i];
			this.list[i] = list[i];
			
			IntDomain oldFD = mappingValuesToIndex.get(listElement);
			if (oldFD == null)
				mappingValuesToIndex.put(listElement, new IntervalDomain(i + 1 + this.indexOffset, i + 1 + this.indexOffset));
			else
				oldFD.unionAdapt(i + 1 + this.indexOffset, i + 1 + this.indexOffset);
			
		}

	}

	/**
	 * It constructs an element constraint with default indexOffset equal 0.
	 * 
	 * @param index index variable.
	 * @param list list containing variables which one pointed out by index variable is made equal to value variable.  
	 * @param value a value variable equal to the specified element from the list. 
	 */
	public ElementInteger(IntVar index, ArrayList<Integer> list, IntVar value) {

		this(index, list, value, 0);
		
	}

	/**
	 * It constructs an element constraint. 
	 * 
	 * @param index variable index
	 * @param list list of integers from which an index-th element is taken
	 * @param value a value of the index-th element from list
	 * @param indexOffset shift applied to index variable. 
	 */
	public ElementInteger(IntVar index, ArrayList<Integer> list, IntVar value, int indexOffset) {

		int [] listOfInts = new int[list.size()];
		for (int i = 0; i < list.size(); i++)
			listOfInts[i] = list.get(i);
		
		commonInitialization(index, listOfInts, value, indexOffset);
				
	}

	/**
	 * It constructs an element constraint with indexOffset by default set to 0.  
	 * 
	 * @param index variable index
	 * @param list list of integers from which an index-th element is taken
	 * @param value a value of the index-th element from list
	 */

	ElementInteger(IntVar index, int[] list, IntVar value) {

		this(index, list, value, 0);
		
	}


	@Override
	public ArrayList<Var> arguments() {

		ArrayList<Var> variables = new ArrayList<Var>(2);

		variables.add(index);
		variables.add(value);
		
		return variables;
		
	}

	@Override
	public void removeLevel(int level) {
		if (level == firstConsistencyLevel)
			firstConsistencyCheck = true;
	}

	@Override
	public void consistency(Store store) {

		if (firstConsistencyCheck) {

			index.domain.in(store.level, index, 1 + indexOffset, list.length + indexOffset);
			firstConsistencyCheck = false;
			firstConsistencyLevel = store.level;

		}

		boolean copyOfValueHasChanged = this.valueHasChanged;
		
		if (indexHasChanged) {

			indexHasChanged = false;
			IntDomain indexDom = index.dom().cloneLight();
			IntDomain domValue = new IntervalDomain(5);

			for (IntDomain duplicate : duplicates) {
				if (indexDom.isIntersecting(duplicate)) {
					domValue.unionAdapt(list[duplicate.min() - 1 - indexOffset]);								
				}
				indexDom = indexDom.subtract(duplicate);
			}
			
			for (ValueEnumeration e = indexDom.valueEnumeration(); e.hasMoreElements();) {
				int valueOfElement = list[e.nextElement() - 1 - indexOffset];
				domValue.unionAdapt(valueOfElement);
			}

			value.domain.in(store.level, value, domValue);
			
		}

		if (copyOfValueHasChanged) {

			valueHasChanged = false;
			IntDomain valDom = value.dom();
			IntDomain domIndex = new IntervalDomain(5);

			for (ValueEnumeration e = valDom.valueEnumeration(); e.hasMoreElements();) {
				IntDomain i = mappingValuesToIndex.get(new Integer(e.nextElement()));
				if (i != null)
					domIndex.addDom(i);
			}

			index.domain.in(store.level, index, domIndex);
			indexHasChanged = false;
			
		}
	
	}

	@Override
	public int getConsistencyPruningEvent(Var var) {

		// If consistency function mode
			if (consistencyPruningEvents != null) {
				Integer possibleEvent = consistencyPruningEvents.get(var);
				if (possibleEvent != null)
					return possibleEvent;
			}
			return IntDomain.ANY;
	}

	@Override
	public String id() {
		if (id != null)
			return id;
		else
			return this.getClass().getSimpleName() + numberId;
	}

	@Override
	public void impose(Store store) {

		index.putModelConstraint(this, getConsistencyPruningEvent(index));
		value.putModelConstraint(this, getConsistencyPruningEvent(value));
		store.addChanged(this);
		store.countConstraint();
		
		duplicates = new ArrayList<IntDomain>();
		
		HashMap<Integer, IntDomain> map = new HashMap<Integer, IntDomain>();
		
		for (int pos = 0; pos < list.length; pos++) {
		
			int el = list[pos];
			IntDomain indexes = map.get(el);
			if (indexes == null) {
				indexes = new IntervalDomain(pos + 1, pos + 1);
				map.put(el, indexes);
			}
			else 
				indexes.unionAdapt(pos + 1);
		}
		
		for (IntDomain duplicate: map.values()) {
			if ( duplicate.getSize() > 3 )
				duplicates.add(duplicate);
		}
		
		valueHasChanged = true;
		indexHasChanged = true;
		
	}

	int indexOf(int element) {
		boolean found = false;
		int i = 0;
		while (!found && i < list.length) {
			found = list[i] == element;
			i++;
		}
		return i - 1;
	}

	@Override
	public void queueVariable(int level, Var var) {
		if (var == index)
			indexHasChanged = true;
		else
			valueHasChanged = true;
	}

	@Override
	public void removeConstraint() {
		index.removeConstraint(this);
		value.removeConstraint(this);
	}

	@Override
	public boolean satisfied() {
		boolean sat = value.singleton();
		if (sat) {
			int v = value.min();
			ValueEnumeration e = index.domain.valueEnumeration();
			while (sat && e.hasMoreElements()) {
				sat = list[e.nextElement() - 1 - indexOffset] == v;
			}
		}
		return sat;
	}

	@Override
	public String toString() {
		
		StringBuffer result = new StringBuffer( id() );
		
		result.append(" : elementInteger").append("( ").append(index).append(", [");
		
		for (int i = 0; i < list.length; i++) {
			result.append( list[i] );
			
			if (i < list.length - 1)
				result.append(", ");
		}
		
		result.append("], ").append(value).append(" )");

		return result.toString();
	}

    @Override
	public void increaseWeight() {
		if (increaseWeight) {
			index.weight++;
			value.weight++;
		}
	}

}
